"""
https://leetcode.cn/problems/coin-change/description/

322. 零钱兑换
已解答
中等
相关标签
相关企业
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

 

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
 

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
"""

from typing import List


class Solution:
    """
    可以用f(n)表示凑齐金额为n所需要的最小硬币。
    可以创建一个表t(...coins_nums)表示每个硬币的数量，假定coins是一个递增数组。

    转换下题意：
    即：coins[0]*t[0]+coins[1]*t[1]+...+coins[n]*t[n]=amount
    其中数组t中的数量>=0。
    求：
    1. 能否匹配到一个数组t，如果不能，返回-1
    2. 如果能匹配，求min(sum(t))
    这个需求中的参数包括：n,amount

    该题目等价于：
    coins[0]*t[0]+coins[1]*t[1]+...+coins[n-1]*t[n-1]=amount
    与
    coins[0]*t[0]+coins[1]*t[1]+...+coins[n]*(t[n]-1)=amount-coins[n]
    以上两者中的最大值。

    
    或者换种思想：
    维护一个数组min_count(amount)表示构建金额amount所需的最小数量，该结果可能为-1。
    t[0]=0,
    则t[amount]=min(t[amount-coins[0]],t[amount-coins[1]],...,t[amount-coins[n]])+1
    需要注意，如果t[?]<0,则不参与计算。

    """

    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount==0:
            return 0
        t=[-1]*amount

        def get_min(idxs:List[int])->int:
            min_count=None
            for idx in idxs:
                if idx>=0 and t[idx]!=-1:
                    min_count=min(min_count,t[idx]) if min_count is not None else t[idx]
            return min_count
        
        def get_min_by_idx(idx:int)->int:
            idxs=[idx-_ for _ in coins if _<=idx]
            min_count=get_min(idxs)
            return min_count+1 if min_count is not None else -1


        t[0]=0
        for i in range(1,amount):
            t[i]=get_min_by_idx(i)

        # print(t)
        return get_min_by_idx(amount)

if __name__=='__main__':
    coins=[1]
    amount=0

    sol=Solution()
    res=sol.coinChange(coins,amount)
    print(res)

    pass